#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

    struct ListNode* swapPairs(struct ListNode* head){
        if(head == NULL || head->next == NULL) return head;

        //伪造出头来
        struct ListNode* headIndex = (struct ListNode*)malloc(sizeof(struct ListNode));
        headIndex->val = -1;
        headIndex->next = head;

        //头指针
        struct ListNode* p = headIndex->next;

        struct ListNode* p0 = headIndex;

        while (p != NULL && p->next != NULL) {
            //缓存下一个结点
            struct ListNode* saveNode = p->next;
            p->next = saveNode->next;
            saveNode->next = p;
            p0->next = saveNode;

            p = p->next;
            p0 = p0->next->next;
        }

        return headIndex->next;
    }

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    if(head == NULL || head->next == NULL) return NULL;
    //求链表长度
    struct ListNode* p = head;
    int flag = 0;
    while (p != NULL && p->next != NULL) {
        struct ListNode* temp = p->next;
        for(int i = 0;i < n;i++) {
            if(temp == NULL) {
                flag = 1;
                break;
            }
            temp = temp->next;
        }
        if(flag == 1) {
            return head->next;
        }
        if(temp != NULL) {
            p = p->next;
        }else {
            p->next = p->next->next;
            return head;
        }
    }
    return head;
}

//struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
//    if(head == NULL || head->next == NULL) return NULL;
//    //求链表长度
//    struct ListNode* p = head;
//    int size = 0;
//    while (p != NULL)  {
//        size++;
//        p = p->next;
//    }
//
//    if(n == size) return head->next;
//
//    p = head;
//    for(int i = 2;i <= size - n;i++ ) {
//        p = p->next;
//    }
//
//    p->next = p->next->next;
//
//    return head;
//}

struct ListNode* deleteDuplicates(struct ListNode* head){
    if(head == NULL) return NULL;

    struct ListNode* p1 = head;
    struct ListNode* p2 = head->next;

    while (p2 != NULL) {
        if(p2->val == p1->val) {
            p1->next = p2->next;
            p2 = p2->next;
        }else {
            p2 = p2->next;
            p1 = p1->next;
        }
    }
    return head;
}

//struct ListNode* deleteDuplicates(struct ListNode* head){
//        if(head == NULL) return NULL;
//
//        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
//        newNode->val = head->val;
//        newNode->next = NULL;
//
//        struct ListNode* p = newNode;
//        while(head != NULL) {
//            if(head->val != p->val) {
//                p->next = head;
//                p = p->next;
//            }else {
//                head = head->next;
//                p->next = NULL;
//            }
//        }
//        return newNode;
//}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA == NULL || headB == NULL) return NULL;

    struct ListNode* pA = headA;
    struct ListNode* pB = headB;

    int sizeA = 0;
    int sizeB = 0;
    while (pA != NULL || pB != NULL) {
        if(pA != NULL) {
            sizeA++;
            pA = pA->next;
        }
        if(pB != NULL) {
            sizeB++;
            pB = pB->next;
        }
    }

    pA = headA;
    pB = headB;
    if(sizeA > sizeB) {
        for(int i = 0;i < sizeA - sizeB;i++) {
            pA = pA->next;
        }
    }else {
        for(int i = 0;i < sizeB - sizeA;i++) {
            pB = pB->next;
        }
    }

    while (pA != pB ) {
        if(pA == NULL || pB == NULL) return NULL;

        pA = pA->next;
        pB = pB->next;
    }

    return pA;
}

//struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//        if(headA == NULL || headB == NULL) return NULL;
//        while (headA != NULL) {
//            struct ListNode* p = headB;
//            while (p != NULL) {
//                if(headA == p) {
//                    return headA;
//                }
//                p = p->next;
//            }
//            headA = headA->next;
//        }
//        return NULL;
//}

struct ListNode* middleNode(struct ListNode* head){
    if(head == NULL) return NULL;
    //定义快慢指针
    struct ListNode* p1 = head; //快指针
    struct ListNode* p2 = head; //慢指针

    //1-2-3-4-5

    //p1走两步，p2走一步
    while(p2 != NULL && p2->next != NULL) {
        p1 = p1->next;
        p2 = p2->next->next;
    }
    return p1;
}

//struct ListNode* middleNode(struct ListNode* head){
//    if(head == NULL) return NULL;
//    //定义辅助指针
//    struct ListNode* pCurrent = head;
//    //获取链表的长度
//    int count = 0;
//    while(pCurrent != NULL) {
//        count++;
//        pCurrent = pCurrent->next;
//    }
//
//    pCurrent = head;
//
//    //如果是奇数
//    for(int i = 2;i <= count/2 + 1;i++ ) {
//        pCurrent = pCurrent->next;
//    }
//    return pCurrent;
//}

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL) return head;

    struct ListNode* newNode = reverseList(head->next);

    head->next->next = head;
    head->next = NULL;

    return newNode;
}

//struct ListNode* reverseList(struct ListNode* head){
//        if(head == NULL) return NULL;
//        //构造头指针
//        struct ListNode* index = (struct ListNode*)malloc(sizeof(struct ListNode));
//        index->val = -1;
//        index->next = head;
//
//        struct ListNode* pCurrent = head;
//        while (pCurrent->next != NULL) {
//            //使辅助移动到最后
//            pCurrent = pCurrent->next;
//        }
//
//        while (index->next != pCurrent) {
//            struct ListNode* temp = index->next;
//            index->next = temp->next;
//            temp->next = pCurrent->next;
//            pCurrent->next = temp;
//        }
//
//        return index->next;
//}

bool hasCycle(struct ListNode *head) {
    if(head == NULL || head->next == NULL)
        return false;

    //快慢指针法
    struct ListNode* p1 = head;     //快指针
    struct ListNode* p2 = head;     //慢指针

    while(p1 != NULL && p2 != NULL && p1->next != NULL) {
        p1 = p1->next;

        if(p1 == p2) {
            return true;
        }
        p2 = p2->next;
        p1 = p1->next;
    }
    return false;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){

    struct ListNode* list = (struct ListNode*)malloc(sizeof(struct ListNode));
    list->val = -1;     //定义输出链表
    list->next = NULL;
    struct ListNode* p = list;

    int num = 0; //进位数字
    int x = 0;  //记录l1链表的值
    int y = 0;  //记录12链表的值
    //遍历两个链表
    while(l1 != NULL ||l2 != NULL) {
        x  = l1 == NULL ? 0 : l1->val;
        y  = l2 == NULL ? 0 : l2->val;

        int sum = x + y + num;
        if(sum < 10) {
            struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
            temp->val = sum;
            temp->next = NULL;
            p->next = temp;
            num = 0;
        }else {
            struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
            temp->val = sum % 10;
            temp->next = NULL;
            p->next = temp;
            num = sum / 10;
        }

        if(l1 != NULL)  l1 = l1->next;
        if(l2 != NULL)  l2 = l2->next;
        p = p->next;
    }
    if (num != 0) {
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->val = num;
        temp->next = NULL;

        p->next = temp;
    }

    return list->next;
}

struct ListNode* rotateRight(struct ListNode* head, int k){

    if(head == NULL) return NULL;
    //1,需要知道链表的长度
    struct ListNode* pCurrent = head;
    int count = 1;
    while(pCurrent->next != NULL) {
        //计数
        count++;
        //向下
        pCurrent = pCurrent->next;
    }
    //循环结束后，指向的是最后一个结点，对接成循环链表
//        System.out.println(count);
    pCurrent->next = head;
    //指向头,循环链表
    pCurrent = pCurrent->next;
    //计算有效循环
    int total = k % count;
    //计算顺转次数
    total = count - total;
//        System.out.println(total);
    for(int i = 1;i < total;i++) {
        pCurrent = pCurrent->next;
    }
    //保存下一个结点
    struct ListNode* saveNode = pCurrent->next;
    pCurrent->next = NULL;
    return saveNode;
}

bool isPalindrome(struct ListNode* head){
    //定义一个辅助指针，用来遍历链表
    struct ListNode* pCurrent = head;
    //当链表不为null时，就一直循环
    int count = 0;
    while (pCurrent != NULL) {
        //计数
        count++;
        pCurrent = pCurrent->next;
    }
    if(count == 0)
        return true;
    //再来一论，装进数组
    pCurrent = head;
    int arr[count];
    for(int i = 0;i < count;i++) {
        arr[i] = pCurrent->val;
        pCurrent = pCurrent->next;
    }
    //遍历集合，看首尾是否相等
    for(int i = 0;i < count / 2;i++) {
        if(arr[i] != arr[count - i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    __int128_t x = 1000000000000000000000000000001;
}